package _02_链表;

/**
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 * @Author: haogege
 * @Date: 2021/9/5
 */
public class _23_合并K个升序链表 {


    public static void main(String[] args) {

        ListNode[] nodes = new ListNode[3];
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;

        ListNode node4 = new ListNode(1);
        ListNode node5= new ListNode(3);
        ListNode node6 = new ListNode(4);
        node4.next = node5;
        node5.next = node6;

        ListNode node7 = new ListNode(2);
        ListNode node8= new ListNode(6);
        node7.next = node8;

        nodes[0] = node1;
        nodes[1] = node4;
        nodes[2] = node7;
        ListNode listNode = mergeKLists(nodes);
    }


    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }


    // 0 3

    // 将数组合并为2个有序数组
    public static ListNode merge(ListNode[] listNodes, int begin, int end) {
        if (end - begin < 1) return listNodes[begin];

        int mid = (end + begin) >> 1;

        ListNode node1 = merge(listNodes, begin, mid);
        ListNode node2 = merge(listNodes, mid + 1, end);

        ListNode listNode = new ListNode(0);
        // 指向当前节点
        ListNode cur = listNode;
        while (node1 != null && node2 != null) {
            if (node1.val < node2.val) {
                cur.next = node1;
                node1 = node1.next;
            } else {
                cur.next = node2;
                node2 = node2.next;
            }
            cur = cur.next;
        }
        if (node1 == null) {
            cur.next = node2;
        } else {
            cur.next = node1;
        }
        return listNode.next;
    }

}
